home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 395_01 / avl / sldel.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-04  |  6.0 KB  |  241 lines
  1. /* implementation file for delete element function for
  2.    sorted list data structure.  implemented as an AVL tree. */
  3.  
  4. #include <string.h>
  5.  
  6. #include "align.h"
  7. #include "stckallc.h"
  8. #include "sortlist.h"
  9. #include "slintrnl.h"
  10.  
  11. /* function which returns a pointer to the pointer to the
  12.    node containing a particular element */
  13. static void **find_node
  14.   (
  15.     /* pointer to sorted list to containing element */
  16.     SORT_LIST *sl,
  17.     /* element to find */
  18.     const void *elem
  19.   )
  20.   {
  21.     /* parent of node containing element */
  22.     void *parent_node;
  23.  
  24.     int compare_result, which_branch;
  25.     void *p = sl->tree;
  26.  
  27.     parent_node = (void *) 0;
  28.  
  29.     for ( ; ; )
  30.       {
  31.     /* compare with current element */
  32.     compare_result = (*(sl->elem_elem_compare))(elem, ELEM_IN_NODE(p));
  33.  
  34.     if (compare_result == 0)
  35.       /* done */
  36.       {
  37.         if (parent_node)
  38.           return(&(NODE(parent_node)->branch[which_branch]));
  39.         else
  40.           /* element in root node */
  41.           return(&(sl->tree));
  42.       }
  43.  
  44.     which_branch = 
  45.       compare_result > 0 ? GREATER_BRANCH : LESS_BRANCH;
  46.  
  47.     /* proceed to next subtree */
  48.     parent_node = p;
  49.     p = NODE(p)->branch[which_branch];
  50.  
  51.       } /* for */
  52.  
  53.   }
  54.  
  55. /* deallocate a given node */
  56. static void free_node
  57.   (
  58.     /* pointer to sorted list in whose node allocation stack the node
  59.        appears */
  60.     SORT_LIST *sl,
  61.     /* pointer to node to free */
  62.     void *node
  63.   )
  64.   {
  65.     void *last_alloc = look_alloc_stack(&(sl->node_alloc_stack));
  66.  
  67.     if (node != last_alloc)
  68.       {
  69.     /* copy the node at the top of the allocation stack to
  70.        the memory occupied by the node to be deleted. */
  71.         memcpy(node, last_alloc,
  72.                N_UNITS_IN_NODE_PREFIX * sizeof(ALIGN_TYPE) + sl->elem_size);
  73.  
  74.     /* find the pointer in the tree to the node that is at the
  75.        top of the allocation stack and reset it to the copy just
  76.            made. */
  77.     *find_node(sl, ELEM_IN_NODE(last_alloc)) = node;
  78.       }
  79.  
  80.     /* dellocate the memory for the node at the top of the
  81.        allocation stack */
  82.     free_alloc_stack(&(sl->node_alloc_stack));
  83.  
  84.     return;
  85.   }
  86.  
  87. /* remove max. or min. node in a tree.  returns non-zero
  88.    if the depth of the tree was reduced.  recursive. */
  89. static int remove_extreme
  90.   (
  91.     /* pointer to pointer to tree to delete from */
  92.     void **tree,
  93.     /* LESS_BRANCH for min., GREATER_BRANCH for max. */
  94.     int which_branch,
  95.     /* pointer to variable to set to node that was removed */
  96.     void **node
  97.   )
  98.   {
  99.     if (!(NODE(*tree)->branch[which_branch]))
  100.       {
  101.     *node = *tree;
  102.     *tree = NODE(*tree)->branch[OTHER(which_branch)];
  103.     return(1);
  104.       }
  105.     else if (remove_extreme(&(NODE(*tree)->branch[which_branch]),
  106.                 which_branch, node))
  107.       /* subtree was reduced in depth */
  108.       {
  109.     int i = NODE(*tree)->balance;
  110.  
  111.     NODE(*tree)->balance = (char)
  112.           (i + (which_branch == LESS_BRANCH ? 1 : -1));
  113.  
  114.     /* if shorter branch was reduced, tree needs to be
  115.            rebalanced */
  116.     if (which_branch == GREATER_BRANCH)
  117.       i = -i;
  118.     if (i == 1)
  119.       i = balance_tree(tree);
  120.  
  121.     return(i);
  122.       }
  123.     else
  124.       /* if branch wasn't reduced in depth, tree wasn't reduced in
  125.      depth */
  126.       return(0);
  127.   }
  128.  
  129. /* unchanging parameters to remove_elem() */
  130. typedef struct
  131.   {
  132.     /* key of element to remove */
  133.     const void *key;
  134.     /* key - element compare function */
  135.     int (*key_elem_compare)(const void *key, const void *elem);
  136.     /* set to node containng element.  needs to be deallocated.  if
  137.        pointer is set to null, no element with the given key found */
  138.     void *node;
  139.   }
  140. RE_PARAM;
  141.  
  142. /* remove element with given key from tree.  returns non-zero
  143.    if the depth of the tree was reduced.  recursive. */
  144. static int remove_elem
  145.   (
  146.     /* pointer to pointer to tree to delete from */
  147.     void **tree,
  148.     /* pointer to unchanging parameters */
  149.     RE_PARAM *param
  150.   )
  151.   {
  152.     int i, j;
  153.  
  154.     if (!*tree)
  155.       {
  156.     param->node = (void *) 0;
  157.     return(0);
  158.       }
  159.  
  160.     i = (*(param->key_elem_compare))(param->key, ELEM_IN_NODE(*tree));
  161.  
  162.     if (i == 0)
  163.       /* found the element to delete */
  164.       {
  165.     void *p;
  166.  
  167.     if (!(NODE(*tree)->branch[LESS_BRANCH] ||
  168.           NODE(*tree)->branch[GREATER_BRANCH]))
  169.       /* no subtrees - just prune the node */
  170.       {
  171.         param->node = *tree;
  172.         *tree = (void *) 0;
  173.         return(1);
  174.       }
  175.  
  176.     /* have to move the extreme node from a subtree into
  177.        this position.  get the extreme node from the deeper
  178.        subtree if possible. */
  179.     i = NODE(*tree)->balance > 0 ? GREATER_BRANCH : LESS_BRANCH;
  180.     j = remove_extreme(&(NODE(*tree)->branch[i]), OTHER(i), &p);
  181.     memcpy(p, *tree, sizeof(NODE_PREFIX));
  182.     param->node = *tree;
  183.     *tree = p;
  184.       }
  185.     else /* proceed to next level */
  186.       {
  187.     i = i > 0 ? GREATER_BRANCH : LESS_BRANCH;
  188.     j = remove_elem(&(NODE(*tree)->branch[i]), param);
  189.       }
  190.  
  191.     if (j)
  192.       /* subtree was reduced in depth */
  193.       {
  194.     j = NODE(*tree)->balance;
  195.  
  196.     /* adjust balance factor */
  197.     NODE(*tree)->balance = (char) (j + (i == LESS_BRANCH ? 1 : -1));
  198.  
  199.         /* if short subtree was reduced, need to rebalance */
  200.     if (i == GREATER_BRANCH)
  201.       j = -j;
  202.     if (j == 1)
  203.       j = balance_tree(tree);
  204.       }
  205.  
  206.     return(j);
  207.   }
  208.  
  209. /* delete the element with the given key. returns SL_SUCCESS if
  210.    element is found.  returns SL_NO_MATCH if element not found. */
  211. SL_RESULT delete_sort_list
  212.   (
  213.     /* sorted list to search */
  214.     SORT_LIST *sl,
  215.     /* key to match */
  216.     const void *key,
  217.     /* pointer to variable to receive a copy of the element searched
  218.        for.  if this pointer is null, the element is simply deleted
  219.        without being copied. */
  220.     void *elem
  221.   )
  222.   {
  223.     RE_PARAM param;
  224.  
  225.     param.key = key;
  226.     param.key_elem_compare = sl->key_elem_compare;
  227.  
  228.     remove_elem(&(sl->tree), ¶m);
  229.  
  230.     if (!param.node)
  231.       return(SL_NO_MATCH);
  232.  
  233.     if (elem)
  234.       memcpy(elem, ELEM_IN_NODE(param.node), sl->elem_size);
  235.  
  236.     /* deallocate node */
  237.     free_node(sl, param.node);
  238.  
  239.     return(SL_SUCCESS);
  240.   }
  241.